package LearnDataStructure.b_散列结构.应用BloomFilter;

import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-05 20:46
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.b_散列结构.应用BloomFilter
 */
public class MyBloomFilter {
    private static final int NUM_SLOTS = 1024 * 1024 * 8;//位图长度
    private static final int NUM_HASH = 8;//hash函数个数
    private BigInteger bitmap = new BigInteger("0");

    /**
     * 所生成的数，代表需要将1左移的位数
     * @param message
     * @param n
     * @return
     */
    public int hash(String message, int n) {
        message = message + String.valueOf(n);
        try {
            MessageDigest md5 = MessageDigest.getInstance("md5");//将任意输入映射成128位（16个字节）整数的hash函数
            byte[] bytes = message.getBytes();//获得原数据的二进制格式

            //hash操作
            md5.update(bytes);
            byte[] digest = md5.digest();

            BigInteger bigInteger = new BigInteger(digest);//至此，获得message + n的md5结果（128位整数）
            return Math.abs(bigInteger.intValue()) % NUM_SLOTS;
        } catch (NoSuchAlgorithmException e) {
            Logger.getLogger(MyBloomFilter.class.getName()).log(Level.SEVERE, null, e);
        }
        return -1;
    }

    public void addElement(String message) {
        for (int i = 0; i < NUM_HASH; i++) {
            int hashCode = hash(message,i);//代表了hash1，hash2……hash8
            if (!bitmap.testBit(hashCode)) {//!bitmap.testBit(hashCode)结果，用于标注位图的该位为1
                bitmap = bitmap.or(new BigInteger("1").shiftLeft(hashCode));//标注位图的该位为1
            }
        }
    }

    public boolean check(String message) {
        for (int i = 0; i < NUM_HASH; i++) {
            int hashCode = hash(message,i);//hashcode代表一个位置
            if (!bitmap.testBit(hashCode)) {//如果位图的该位为0，那么message一定不存在
                return false;
            }
        }
        return true;//不精确，有可能误判
    }

    public static void main(String[] args) {
        MyBloomFilter test = new MyBloomFilter();
        List<String> list = new ArrayList<>();
        list.add("abc");
        list.add("def");
        list.add("ghi");
        list.add("jkl");

        for (int i = 0; i < list.size(); i++) {
            test.addElement(list.get(i));
        }

        System.out.println(test.check("abc"));
        System.out.println(test.check("wyl"));
    }
}
